class Solution {
private:
	
	struct cmp1{
		bool operator () (pair<int, int>& a, pair<int, int>& b){
			return a.first > b.first;
		}
	};
	
	static bool cmp(vector<int>& a, vector<int>& b){
		return a[0] < b[0];
	}
	
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp1> pq;
	priority_queue<int, vector<int>, greater<int>> next_num;
public:
    int smallestChair(vector<vector<int>>& times, int targetFriend) {
		int target = times[targetFriend][0], cnt = 0, temp = 0;
        sort(times.begin(), times.end(), cmp);
		for(int i = 0; i <= times.size(); i++)next_num.push(i);
		while(true){
			cnt++;
			while(!pq.empty() && pq.top().first == cnt){
				next_num.push(pq.top().second);
				pq.pop();
			}
			if(cnt == target)break;
			if(cnt == times[temp][0]){
				pq.push(pair<int, int>(times[temp][1], next_num.top()));
				next_num.pop();
				temp++;
			}
		}
		return next_num.top();
    }
};
